We propose a phase I/II clinical trial evaluating the safety and bio-efficacy of combinant vaccinia-PSA in the treatment of PSA recurrence following radical prostatectomy. The trial is based on preliminary data from the Principal Investigator, as well as reports published by others demonstrating the pre-clinical efficacy of recombinant vaccines for prostate cancer. The proposed trial is unique from other cancer vaccine trials in focusing on microscopic post-prostatectomy recurrence and in using concurrent androgen deprivation to minimize tumor volume and prostate-spcific immunological tolerance/anergy. This study will supersede all other clinical trials for PSA recurrence following radical prostatectomy at our institution.